#include<cstdio>
#include<iostream>
#include<cctype>
#include<algorithm>
using namespace std;
inline void read(int &x){
  #if 1
    char ch=getchar();int f=1;x=0;
    while(!isdigit(ch) && ch^'-') ch=getchar();
    if(ch=='-') f=-1,ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    x*=f;
  #else
  cin>>x;
  #endif
}
const int maxn = 1e6+7;
int n, m;
int a[maxn];
int fen[maxn], vis[maxn];
int res[maxn];
int lsb(int x) {return x&-x;}
void add(int i, int val) {
  while(i<=n) { fen[i]+=val; i+=lsb(i);}
}
int query(int i) {
  int ans = 0;
  while(i>0) { ans += fen[i]; i-=lsb(i);}
  return ans;
}
struct Q {  int l, r, i; }que[maxn];

int main() {
  read(n); for(int i=1; i<=n; ++i) read(a[i]);
  read(m); for(int i=1; i<=m; ++i) read(que[i].l), read(que[i].r), que[i].i=i;

  sort(que+1, que+m+1, [](const Q&a, const Q&b) {
    return a.r<b.r;
  });
  int now = 1;
  for(int i=1; i<=m; ++i) {
    for(int j=now; j<=que[i].r; ++j) {
      if(vis[a[j]]) add(vis[a[j]], -1);
      add(j, 1);
      vis[a[j]] = j;
    }
    now = que[i].r + 1;
    res[que[i].i] = query(que[i].r) - query(que[i].l-1);
  }
  for(int i=1; i<=m; ++i) printf("%d\n", res[i]);
  return 0;
}
